package datastructure.queue;


import java.util.Arrays;

/**
 * @author XY
 * @version 1.0
 * @date 2021/9/2 14:54
 * @Description 循环队列
 */
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    //front与tail一个指向队首，一个只想队尾，如果相等则说明队列为空
    private int front,tail;
    //方便代码的可读性，也可以不加这个参数
    private int size;

    public LoopQueue(int capacity){
        //这里+1是因为循环队列会多出一个空闲的位置，需要将这个位置算上去
        data=(E[])new Object[capacity+1];
        front=0;
        tail=0;
        size=0;
    }

    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length-1;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        //这里是否可用 size==0
        return front==tail;
    }

    @Override
    public void enqueue(E e) {
        if((tail+1)%data.length==front){
            resize(getCapacity()*2);
        }
        data[tail] = e;
        tail=(tail+1)%data.length;
        size++;
    }

    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new RuntimeException("Cannot dequeue from an empty queue");
        }
        E ret =data[front];
        data[front]=null;
        front=(front+1)%data.length;
        size--;
        //缩容
        if(size==getCapacity()/4 && getCapacity()/2!=0){
            resize(getCapacity()/2);
        }
        return ret;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new RuntimeException("Cannot dequeue from an empty queue");
        }
        return data[front];
    }

    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity+1];
        for (int i = 0; i < size; i++) {
            //有可能数组会越界，需要求个模,因为是循环队列，有些元素可能在front的前面
            newData[i]=data[(front+i)%data.length];
        }
        data = newData;
        front = 0 ;
        tail=size;
    }

    @Override
    public String toString() {
        return "LoopQueue{" +
                "data=" + Arrays.toString(data) +
                ", front=" + front +
                ", tail=" + tail +
                ", size=" + size +
                '}';
    }
}
